1. Technical Field
This invention relates to computer aided design and more particularly to an element placement method for optimally assigning a plurality of different size elements to element positions in an array of element positions.
In the present state of the art, computer aided design techniques are used in various phases of the design of an electronic system. Computer aided design may be used to design one or more elements of the electronic system. Then, element placement programs may be employed to place the different size elements on their next level package according to predefined interconnection requirements. The next level package may be viewed as defining an array of possible element placement positions thereon. Other computer aided design programs may be used for designing the specific wiring paths between the elements on their next level package.
Element placement programs are employed for generating an optimized placement of elements on their next level package. The elements to be placed may be macros, i.e., a group of related circuits for performing a given function, which are placed on a first level package, e.g., a large scale integrated circuit chip or a semiconductor wafer. Alternatively, the elements may be a plurality of different size electronic components, e.g., large scale integrated circuits, resistors, capacitors, etc., which are placed on a second level package, e.g., a printed circuit board or card, or a multilayer ceramic substrate. Also, the elements to be placed may be printed circuit boards or cards, which are placed on a third level package, e.g., a motherboard. An element placement program must generate an element layout which simplifies the routing of the element interconnections on the next level package and also obeys various physical, technology and other constraints. Physical constraints include the requirement that the elements must not overlap each other or extend over the side of the next level package. Technology constraints relate to the limited amount of wiring space which is available to make the many interconnections between the elements. Other constraints may relate to the preassigned position of input/output connections, test points and the like imposed by the system designer.
2. Background Art
Many element placement programs and techniques are known in the art. However, known placement programs and techniques often do not properly handle the complexity of placing a plurality of different size elements while satisfying wireability constraints. As the number and complexity of elements increase and the element packing density increases, the required computer running time for known automatic element placement programs becomes prohibitive. Moreover, the resulting placement is often not optimum in terms of component fit and rule violations.
An example of a known element placement technique is described in U.S. Pat. No. 3,654,615 entitled "Element Placement System" and assigned to the assignee of the present invention. Disclosed in an element placement system wherein the elements are first ordered according to the degree of electrical interconnectivity they have to other elements to be placed on the second level package. The element with the highest degree of connectivity is assigned a location a central portion on the second level package, then the next element is assigned adjacent to the first, and elements continue to be assigned one by one until all of the elements are assigned.
Another example of a known element placement program is described in U.S. Pat. No. 3,681,782 entitled "Machine Process for Positioning Interconnected Components to Minimize Interconnecting Line Length". Disclosed is an element placement program which breaks the elements into nets having two components, three components, etc. and successively places the nets on the next level package until all the nets have been placed.
An overview of element placement techniques is provided in Chapter 5 of Design Automation of Digital Systems-Theory and Techniques, Vol. 1, by M. Hanan and J. M. Kurtzberg, edited by M. A. Breur (Prentice Hall, 1972). While the above examples illustrate known element placement programs, there is a present need for more versatile placement programs (i.e., programs which place a plurality of different size elements automatically and efficiently) so that the highly complex combinatorial problem of placing these elements may be solved.